import java.util.Deque;
import java.util.LinkedList;

public class Trap {
    // 接雨水
    // https://leetcode.cn/problems/trapping-rain-water/?envType=study-plan-v2&envId=top-100-liked
    public int trap1(int[] height) {
        // 通过两次预处理，分别找出第i个元素左边和右边的最高的柱子
        // 然后再遍历一遍数组，那么当前位置可以接的雨水的体积就是：
        // 该元素左右两侧最高柱子的较小值-当前位置柱子的高度
        // Math.min(leftMaxHeight[i], rightMaxLength[i]) - height[i]
        int len = height.length;
        int[] leftMaxHeight = new int[len];
        int[] rightMaxLength = new int[len];
        int max = 0;
        for (int i = 0; i < len; i++) {
            leftMaxHeight[i] = max;
            max = Math.max(max, height[i]);
        }
        max = 0;
        for (int i = len-1; i>= 0; i--) {
            rightMaxLength[i] = max;
            max = Math.max(max, height[i]);
        }
        int ret = 0;
        for (int i = 1; i < len-1; i++) {
            ret += Math.max(Math.min(leftMaxHeight[i], rightMaxLength[i]) - height[i], 0);
        }
        return ret;
    }

    public int trap(int[] height) {
        // 通过单调栈：从栈顶（数组头）到栈底（数组尾）的元素是单调递增的
        // 如果当前位置的柱子高度低于或者等于栈顶元素的话，那么直接入栈
        // 如果当前元素的柱子高度高于栈顶的话，那么当前位置可以作为接雨水的右边界
        // 栈顶元素就是可以接雨水的柱子的高度，栈顶元素下面的元素就是左边界
        Deque<Integer> deque = new LinkedList<>();
        int ret = 0;
        for (int i = 0; i < height.length; i++) {
            if (deque.isEmpty() || height[i] <= height[deque.peekFirst()]) {
                deque.offerFirst(i);
            } else {
                while (!deque.isEmpty() && height[i] > height[deque.peekFirst()]) {
                    int mid = deque.pollFirst();
                    if (deque.isEmpty()) {
                        break;
                    }
                    int left = deque.peekFirst();
                    ret += (Math.min(height[i], height[left]) - height[mid]) * (i-left-1);
                }
                deque.addFirst(i);
            }
        }
        return ret;
    }

    public static void main(String[] args) {
        int[] height = {0,1,0,2,1,0,1,3,2,1,2,1};
        System.out.println(new Trap().trap(height));
    }
}
